﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace lzp_pack
{
    class Program
    {
        #region Constants

        private const int HashTableSize = 65536;
        private const int LzpMatchFlag = 1;
        private const int LzpNoMatchFlag = 0;
        private const int ContextLength = 2;
        private const int BitsInByte = 8;

        #endregion

        private static List<byte> BitArrayToByteArray(List<byte> ba)
        {
            List<byte> result = new List<byte>();
            byte curResult = 0;
            double m = 1;
            int bytesCount = ba.Count;
            for (int index = 0, bitCounter = 0; index < bytesCount; bitCounter++, index++, m *= 2)
            {
                curResult += ba[index] != 0 ? (byte)m : (byte)0;
                if (bitCounter >= 7)
                {
                    result.Add(curResult);
                    curResult = 0;
                    bitCounter = -1;
                    m = 0.5;
                }
            }
            
            return result;
        }

        private static byte[] ByteToBitArray(byte ByteArray)
        {
            byte[] resultBits = new byte[BitsInByte];
            int dec = ByteArray;
            int j = 0;
            while (dec > 0)
            {
                int remainder = dec%2;
                dec /= 2;
                resultBits[j] = (byte) remainder;
                j++;
            }
            return resultBits;
        }

        private static void Pack(string inputFileName, string outputFileName)
        {
            Dictionary<ushort, int> hashTable = new Dictionary<ushort, int>(HashTableSize);
            List<byte> input = File.ReadAllBytes(inputFileName).ToList();
            List<byte> BitsPack = new List<byte>();

            byte[] lenBytes = BitConverter.GetBytes(input.Count);
            for (int i = 0; i < sizeof (int); i++)
            {
                BitsPack.AddRange(ByteToBitArray(lenBytes[i]));
            }
            int currentOffset = 0;
            ushort hash = GetHash(input, currentOffset);
            hashTable.Add(hash, currentOffset);
            BitsPack.AddRange(ByteToBitArray(input[0]));
            BitsPack.AddRange(ByteToBitArray(input[1]));
            currentOffset += ContextLength;
            while (currentOffset < input.Count)
            {
                hash = GetHash(input, currentOffset - ContextLength);
                if (hashTable.ContainsKey(hash))
                {
                    int matchLenght = GetMatchLenght(input, hashTable[hash] + ContextLength, currentOffset);
                    if (matchLenght == 0)
                    {
                        BitsPack.Add(LzpNoMatchFlag);
                        BitsPack.AddRange(ByteToBitArray(input[currentOffset]));
                        hashTable[hash] = currentOffset - ContextLength;
                        currentOffset++;
                    }
                    if (matchLenght > 0)
                    {
                        BitsPack.Add(LzpMatchFlag);
                        BitsPack.AddRange(ByteToBitArray((byte) matchLenght));
                        hashTable[hash] = currentOffset - ContextLength;
                        currentOffset += matchLenght;
                    }
                }
                else
                {
                    BitsPack.Add(LzpNoMatchFlag);
                    BitsPack.AddRange(ByteToBitArray(input[currentOffset]));
                    hashTable[hash] = currentOffset - ContextLength;
                    currentOffset++;
                }
            }

            while (BitsPack.Count % 8 != 0)
            {
                BitsPack.Add(0);
            }

            var fileBytes = BitArrayToByteArray(BitsPack).ToArray();
            using (FileStream sw = new FileStream(outputFileName, FileMode.OpenOrCreate))
            {
                sw.Write(fileBytes, 0, fileBytes.Length);
            }
        }

        private static int GetMatchLenght(List<byte> input, int offset1, int offset2)
        {
            int match = 0;
            if (offset1 != offset2)
            {
                while (offset1 < input.Count
                       && offset2 < input.Count
                       && input[offset1] == input[offset2])
                {
                    match++;
                    offset1++;
                    offset2++;
                    if (match > 254)
                    {
                        break;
                    }
                }
            }
            return match;
        }

        private static ushort GetHash(List<byte> input, int offset)
        {
            return (ushort)(input[offset + 1] * 256 + input[offset]);
        }

        private static void Unpack(string inputFileName, string outputFileName)
        {
            Dictionary<ushort, int> hashTable = new Dictionary<ushort, int>(HashTableSize);

            byte[] inputBytes = File.ReadAllBytes(inputFileName);
            List<byte> inputBits = new List<byte>();
            foreach (var inputByte in inputBytes)
            {
                inputBits.AddRange(ByteToBitArray(inputByte));
            }

            int offset = 0;

            var fileSizeValueAsByteArray = BitArrayToByteArray(inputBits.GetRange(offset, sizeof (int)*BitsInByte));
            offset += sizeof (int)*BitsInByte;
            int fileSize = BitConverter.ToInt32(fileSizeValueAsByteArray.ToArray(), 0);

            List<byte> unpack = new List<byte>();
            unpack.Add(BitArrayToByteArray(inputBits.GetRange(offset, BitsInByte))[0]);
            offset += BitsInByte;
            unpack.Add(BitArrayToByteArray(inputBits.GetRange(offset, BitsInByte))[0]);
            offset += BitsInByte;
            ushort hash = GetHash(unpack, unpack.Count - 2);
            hashTable.Add(hash, unpack.Count - 2);

            while (unpack.Count < fileSize)
            {
                if (inputBits[offset] == LzpNoMatchFlag)
                {
                    offset++;
                    unpack.Add(BitArrayToByteArray(inputBits.GetRange(offset, BitsInByte))[0]);
                    hash = GetHash(unpack, unpack.Count - 3);
                    hashTable[hash] = unpack.Count - 3;
                    offset += BitsInByte;
                }
                else if (inputBits[offset] == LzpMatchFlag)
                {
                    offset++;
                    hash = GetHash(unpack, unpack.Count - 2);
                    if (hashTable.ContainsKey(hash))
                    {
                        int index = hashTable[hash] + 2;
                        byte matchLength = BitArrayToByteArray(inputBits.GetRange(offset, BitsInByte))[0];
                        for (int i = 0; i < matchLength; i++)
                        {
                            unpack.Add(unpack[index]);
                            index++;
                        }
                        hashTable[hash] = unpack.Count - matchLength - ContextLength;
                        offset += BitsInByte;
                    }
                }
            }

            FileStream fs = new FileStream(outputFileName, FileMode.OpenOrCreate);
            fs.Write(unpack.ToArray(), 0, unpack.Count);
        }

        static void Main(string[] args)
        {
            Pack("Base.log", "CompressedLog.lzp2");
            Unpack("CompressedLog.lzp2", "Uncompressed.log");
        }
    }
}
